//https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/submissions/544528324/

struct TreeNode* deduceTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {

    if (preorderSize == 0)
        return NULL;

    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (node == NULL)
    {
        perror("malloc fail\n");
        return NULL;
    }
    node->val = preorder[0];
    node->left = NULL;
    node->right = NULL;

    int i = 0;
    for (i = 0; i < inorderSize; i++)
    {
        if (inorder[i] == preorder[0])
            break;
    }

    if (i)
        node->left = deduceTree(preorder + 1, i, inorder, i);
    if (inorderSize - i - 1)
        node->right = deduceTree(preorder + 1 + i, preorderSize - i - 1, inorder + i + 1, inorderSize - i - 1);
    return node;

}